#include "status.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef union{
	char d1;
	int d2;
}dataa;
typedef struct{
	dataa dat;
	int flag;//0 char;1 int
}datatype;
/**
  this program is used to distinguish whether an exp is right or not with bracket
  */
typedef struct snode{
	datatype data;
	struct snode *next;
}stack;
status init_stack(stack **s){
	(*s)=NULL;
	return ok;
}
status push(stack **s,datatype e){
	stack* node=(stack*)malloc(sizeof(stack));
	if(!node) exit(overflow);
	node->data=e;
	node->next=*s;
	(*s)=node;
	return ok;
}
status is_empty(stack *s){
	if(s==NULL)
		return ok;
	else 
		return error;
}
status pop(stack **s,datatype *e){
	if(is_empty(*s)){
		return error;
	}
	*e=(*s)->data;
	*s=(*s)->next;
	return ok;
}
status get_top(stack *s,datatype *e){
	if(is_empty(s)){
		return error;
	}
	*e=s->data;
	return ok;
}
void traverse(stack *s){
	stack *p;
	p=s;
	while(p){
		if(p->data.flag==0)
		    printf("%c ",p->data.dat.d1);
		else if(p->data.flag==1)
			printf("%d ",p->data.dat.d2);
		p=p->next;
	}
	printf("\n");
}
int postexp(char str[]){
	//1.mid str->post str
	int x;
	int i=0;
	stack *s,*op_s;
	init_stack(&s);
	init_stack(&op_s);
	while(str[i]!='#'){
		if(str[i]>='0' && str[i]<='9'){
			x=0;
			while(str[i]>='0'&&str[i]<='9'){
				x=(int)(str[i]-48)+x*10;
				i++;
			}
			datatype e;
			e.flag=1;
			e.dat.d2=x;
			push(&s,e);
		}else{
			datatype e;
			e.flag=0;
			e.dat.d1=str[i];
			if(is_empty(op_s) || str[i]=='('){
				push(&op_s,e);
				i++;
				continue;
			}
			datatype e_top;
			get_top(op_s,&e_top);
			if(str[i]==')'){
				datatype tmp;
				while(pop(&op_s,&tmp)&&tmp.dat.d1 != '('){
					datatype op_d;
					op_d.flag=0;
					op_d.dat.d1=tmp.dat.d1;
					push(&s,op_d);
				}
			}else if(e_top.dat.d1=='+' || e_top.dat.d1=='-' || e_top.dat.d1=='('){
				push(&op_s,e);
			}else if((e_top.dat.d1=='*' || e_top.dat.d1=='/' )&&(str[i]=='*' || str[i]=='/')){
				push(&op_s,e);
			}else{
				datatype tmp;
				while(pop(&op_s,&tmp)) {
					datatype op_d;
					op_d.flag=0;
					op_d.dat.d1=tmp.dat.d1;
					push(&s,op_d);
				}
				push(&op_s,e);
			}
			traverse(s);
			traverse(op_s);
			i++;
			continue;
		}
	}
	if(!is_empty(op_s)){
		datatype tmp;
		pop(&op_s,&tmp);
		push(&s,tmp);
	}
	traverse(s);
	traverse(op_s);
	//1.2transfer
	stack *trans;
	init_stack(&trans);
	while(!is_empty(s)){
		datatype tmp;
		pop(&s,&tmp);
		push(&trans,tmp);
	}
	s=trans;
	traverse(s);
	//2.calc
	stack *calc_s;
	init_stack(&calc_s);
	while(!is_empty(s)){
		datatype tmp;
		pop(&s,&tmp);
		if(tmp.flag==1){
			push(&calc_s,tmp);
		}else{
			datatype x1;
			datatype x2;
			pop(&calc_s,&x2);
			pop(&calc_s,&x1);
			switch(tmp.dat.d1){
				case '+':
					x=x1.dat.d2+x2.dat.d2;
					break;
				case '-':
					x=x1.dat.d2-x2.dat.d2;
					break;
				case '*':
					x=x1.dat.d2*x2.dat.d2;
					break;
				case '/':
					x=x1.dat.d2/x2.dat.d2;
					break;
			}
			datatype res;
			res.flag=1;
			res.dat.d2=x;
			push(&calc_s,res);
		}
		traverse(calc_s);
	}
	printf("finished calc\n");
	datatype res;
	pop(&calc_s,&res);
	return res.dat.d2;
}
int main(){
	char exp[]="21*(3+5)+7/1-4#";
	int res=postexp(exp);
	printf("%d\n",res);
}

